import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-11-18
 * Time: 10:27
 */
public class Prac {
    /**
     * 随机链表的复制：
     * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任
     * 何节点或空节点。深拷贝这个链表得到一个相同的新链表(新的对象)。
     */
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static Node copyRandomList(Node head) {
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            Node newCur = map.get(cur);
            newCur.next = map.get(cur.next);
            newCur.random = map.get(cur.random);
            cur = cur.next;
            String a;
        }
        return map.get(head);
    }

    /**
     * 只出现过一次的数字：
     * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现
     * 了一次的元素。
     */
    public static int singleNumber(int[] nums) {
        // //1.异或：
        // int ret = 0;
        // for (int i = 0; i < nums.length; i++){
        //     ret ^= nums[i];
        // }
        // return ret;

        //2.使用Map || Set
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            if (!set.contains(x)) set.add(x);
            else set.remove(x);
        }
        int ret = 0;
        for (int x : set) {
            ret = x;
        }
        return ret;
    }

    /**
     * 宝石与石头：
     * 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
     * stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。字母区分大小写，
     * 因此 "a" 和 "A" 是不同类型的石头。
     */
    public static int numJewelsInStones(String jewels, String stones) {
        //数组方法
        // String[] arr = jewels.split("");
        // String[] arr1 = stones.split("");
        // int count = 0;
        // for (String y : arr){
        //     for (String x : arr1){
        //         if (y.equals(x)){
        //             count++;
        //         }
        //     }
        // }
        // return count;
        //集合方法
        Set<Character> setJ = new HashSet<>();
        int count = 0;
        for (int i = 0; i < jewels.length(); i++) {
            setJ.add(jewels.charAt(i));
        }
        for (int i = 0; i < stones.length(); i++) {
            if (setJ.contains(stones.charAt(i)))
                count++;
        }
        return count;
    }

    /**
     * 坏键盘打字：
     *         旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字
     *     、以及实际被输入的文字，请你列出肯定坏掉的那些键。
     */
    public static void findBad(String str1, String str2) {
        Set<Character> set2 = new HashSet<>();
        for (Character x : str2.toUpperCase().toCharArray()) {
            set2.add(x);
        }
        Set<Character> hasPrint = new HashSet<>();
        for (Character x : str1.toUpperCase().toCharArray()) {
            if (!set2.contains(x) && !hasPrint.contains(x)) {
                System.out.print(x);
                hasPrint.add(x);
            }
        }

    }

    /**
     * 统计每一个数字重复出现的次数
     */
    public static void func(int[] arr){
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : arr){
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        for (int x: map.keySet()){
            System.out.println(x + ":" + map.get(x));
        }
    }

    /**
     * 前k个高频单词
     *         给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。返回的答案应该按单词出
     *     现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序排序。
     */
    public static List<String> topKFrequent(String[] words, int k){
        Map<String, Integer> map = new HashMap<>();
        //计数
        for (String x : words){
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        //频率不一样的时候建立小根堆，频率一样时候建立大根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //放入小根队中
        for (Map.Entry<String, Integer> entry: map.entrySet()){
            //先放满K个数据
            if (minHeap.size() < k){
                minHeap.offer(entry);
            }else{
                //判断频率相等跟频率不相等两种情况
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) == 0){
                    if (top.getKey().compareTo(entry.getKey()) > 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else{
                    if (top.getValue().compareTo(entry.getValue()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        //逆序放入顺序表中
        for(int i = 0; i < k; i++){
            list.add(0, minHeap.poll().getKey());
        }
        return list;
    }
    public static void main(String[] args) {
        System.out.println("========================");
        int[] arr = {1,2,3,2,1,2,1,};
        func(arr);
        System.out.println("========================");
        String[] word = {"a", "b", "c", "c"};
        System.out.println(topKFrequent(word, 3));
    }
}
